# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from collections import deque
from typing import Optional

from python.mypackage import TreeNode


class Solution:

    """
    方法： isSymmetric 递归判断左右子树是否对称
    
    Args:
        root (Optional[TreeNode]): 二叉树的根节点
        
    Returns:
        bool: 如果二叉树是对称的返回True,否则返回False
        
    Time:  
        O(N)，其中 N 为二叉树的节点数。每个节点只会被访问一次。
        
    Space:  
        O(H)，其中 H 为二叉树的高度。递归调用的栈空间取决于二叉树的高度。
    """
    def isSameTree(self, p:Optional[TreeNode], q:Optional[TreeNode]) -> bool:
        if p is None or q is None: return p is q
        return p.val == q.val and self.isSameTree(p.left, q.right) and self.isSameTree(p.right, q.left)
    
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        return self.isSameTree(root.left, root.right)
    
    """
    方法： isSymmetric1 使用队列进行迭代判断左右子树是否对称
    
    Args:
        root (TreeNode): 二叉树的根节点
        
    Returns:
        bool: 如果二叉树是对称的返回True,否则返回False
        
    Time:  
        O(N)，其中 N 为二叉树的节点数。每个节点只会被访问一次。
        
    Space:  
        O(N)，其中 N 为二叉树的节点数。队列中最多可能存储N个节点。
    """
    def isSymmetric1(self, root: TreeNode) -> bool:
        return self.check(root, root)

    def check(self, p: TreeNode, q: TreeNode) -> bool:
        queue = deque([p, q])
        while queue:
            p = queue.popleft()
            q = queue.popleft()
            if p is None and q is None:
                continue
            if (p is None or q is None) or (p.val != q.val):
                return False
            queue.append(p.left)
            queue.append(q.right)
            queue.append(p.right)
            queue.append(q.left)
        return True
        